package com.ctrip.demo.leetcode;

import java.util.HashMap;
import java.util.Map;

public class LeetCode219 {

    public static void main(String[] args) {
        System.out.println(containsNearbyDuplicate(new int[]{1,0,1,1},1));
    }

    public static boolean containsNearbyDuplicate(int[] nums, int k) {

        if(k == 0) {
            return false;
        }
        Map<Integer,Integer> window = new HashMap<>();
        int left = 0, right = 0;
        while(right < nums.length) {
            int rightValue = nums[right];
            // 记录当前指针索引
            int index = right;
            // 移动指针
            right ++;
            window.put(rightValue, window.getOrDefault(rightValue, 0) + 1);
            while(window.get(rightValue) > 1) {
                if(Math.abs(left - index) <= k) {
                    return true;
                }
                // 缩小窗口
                int leftValue = nums[left];
                left ++;
                if(rightValue == leftValue) {
                    window.put(rightValue, window.get(rightValue) - 1);
                }
            }
        }

        return false;


        // Map<Integer,Integer> map = new HashMap<>();

        // for(int i = 0; i < nums.length; i ++) {
        //     if(map.containsKey(nums[i])) {
        //         if(Math.abs(i - map.get(nums[i])) <= k) return true;
        //     }
        //     map.put(nums[i], i);
        // }
        // return false;

    }

}
